package basic_datastructure.heap;

import java.util.Arrays;

public class PriorityQueueTest {
    private int[] arr;
    private int size;
    public PriorityQueueTest(){
        arr = new int[32];
    }

    //入队
    public void enQueue(int key){
        if(size >= arr.length){
            resize();
        }
        arr[size++] = key;
        upAdjust();
    }
    public int deQueue(){
        if(size <= 0){
            return -1;
        }
        int res = arr[0];
        arr[0] = arr[--size];
        downAdjust();
        return res;
    }
    public void upAdjust(){
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        while (childIndex > 0 && arr[childIndex] > arr[parentIndex]){
            swap(arr, childIndex, parentIndex);
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
    }
    public void downAdjust(){
        int parentIndex = 0;
        int childIndex = parentIndex * 2 + 1;
        while(childIndex < size){
            if (childIndex + 1 < size && arr[childIndex + 1] > arr[childIndex]){
                childIndex++;
            }
            if(arr[parentIndex] >= arr[childIndex]){
                break;
            }
            swap(arr, parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }
    public void resize(){
        int newSize = this.size * 2;
        this.arr = Arrays.copyOf(arr, newSize);
    }
    public void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public static void main(String[] args) throws Exception {
        PriorityQueueTest priorityQueue = new PriorityQueueTest();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(12131);
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
        System.out.println("出队元素是：" + priorityQueue.deQueue());
    }
}
